package algorithm.middle;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle
 * @Author: 江岸
 * @CreateTime: 2021-04-28 20:02
 * @Description: 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：c = 5
 * 输出：true
 * 解释：1 * 1 + 2 * 2 = 5
 * 示例 2：
 *
 * 输入：c = 3
 * 输出：false
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sum-of-square-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class JudgeSquareSum633 {
    //枚举法
    public boolean judgeSquareSum(int c) {
        int max = (int) Math.sqrt(c);
        for (int i=0;i<=max;i++){
            int b =  (int) Math.sqrt(c-i*i);
            if (i*i+b*b==c) return true;
        }
        return false;
    }

    //双指针
    public boolean judgeSquareSum2(int c) {
        int right = (int) Math.sqrt(c);
        int left = 0;
        while (left<=right){
            int cur = left*left+right*right;
            if (cur==c){
                return true;
            }else if(cur<c){
                left++;
            }else {
                right--;
            }
        }
        return false;
    }
}
